package LearnAlgorithm.d_标准查找算法and标准排序算法;

import java.util.HashMap;

public class b5c快速排序by单项扫描分区方式plus三分法plus绝对中值优化plus小数组插入排序优化 {
	public static void main(String[] args) {
		int[] arr = new int[] {6,8,7,9,5,4,3,4,4,6,6,6,8,7,9,5,4,3,4,4,6,6};
		long before = System.currentTimeMillis();
		quickSort(arr, 0, arr.length-1);
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	/**
	 * 快速排序
	 * O(NlogN)
	 * @param arr
	 * @param p
	 * @param r
	 */
	public static void quickSort(int[] arr, int p, int r) {//使用递归
		if (p < r) {
			if ((r - p) + 1 <= 8) {
				insertSort(arr, p, r);//当传入的片段，元素个数小于等于8，插入排序 要快于 快速排序
			} else {
				int[] q = partition(arr, p, r);//核心语句在这行，即找出主元
				quickSort(arr, p, q[0]-1);//对主元左边排序
				quickSort(arr, q[1]+1, r);//对主元右边排序
			}
		}
	}
	
	/**
	 * 快速排序核心---设置主元并把主元放在相对居中的位置
	 * 老师的思想---主元是首值
	 * @param arr
	 * @param p
	 * @param r
	 * @return bigger
	 */
	public static int[] partition(int[] arr, int p,  int r) {
		int midIndex =  getMedian(arr, p, r);//寻找绝对中值的索引，使用了插入排序
		swap(arr, p, midIndex);//把绝对中值与首值进行交换
		int pivot = arr[p];//定义首值作为主元pivot
		int sp = p+1;//定义右移指针
		int e = p+1;//定义扫描相同数值的指针
		int bigger = r;//定义左移指针
		int[] arrTemp = new int[2];//这里可以把数组抽取出来成为main的成员变量，节省内存
		while (sp <= bigger) {//只要sp>bigger那么就是交错了，就可以退出循环
			if (arr[sp] < pivot && sp == e) {
				sp++;
				e++;
			} else if (arr[sp] < pivot && sp != e) {
				swap(arr, e, sp);
				sp++;
				e++;
			} else if (arr[sp] == pivot) {
				sp++;
			} else {
				if (sp < bigger) {
					swap(arr, sp, bigger);
				}
				bigger--;
			}
		}
		/*
		 * while(sp <= bigger)退出时，sp/bigger两者交错，
		 * 且bigger指向的是最后一个小于等于主元的位置，
		 * 也就是主元应该呆的位置
		 */
		swap(arr, p, (e-1));//这里理论上也能改进，如arr[p]==arr[biger],如p==bigger的情况，但是我不改进了，我怕出错
		arrTemp[0] = (e-1);
		arrTemp[1] = (bigger);
		return arrTemp;//最后返回由相等元素组成的数组的首尾索引组成的2元素数组
	}
	
	/**
	 * 寻找(宏观上相对的)绝对中值
	 * @param arr
	 * @param p
	 * @param r
	 * @return
	 */
	public static int getMedian(int[] arr, int p, int r) {
		int size = (r - p) + 1;//传入的数组片段长度
		int groupSize = (size % 5 == 0) ? (size / 5) : ((size / 5) + 1);//每5个元素一组，总共有多少组
		int medians[] = new int[groupSize];//保存所有组的中值的数组
		HashMap<Integer, Integer> mediansValue_index = new HashMap<Integer,Integer>();//生成所有需要保存的中值的“数值:索引”map集合
		int indexOfMedians = 0;
		
		for (int j = 0; j < groupSize; j++) {
			if (j == (groupSize - 1)) {//优先考虑最后一组的情况，因为最后一组可能不是5个数
				insertSort(arr, (p + (j * 5)), r);//排序最后一组
				medians[indexOfMedians++] = arr[(p + (j * 5) + r) >>> 1];//把最后一组的中值存入特定数组，除法向下取整
				mediansValue_index.put(arr[(p + (j * 5) + r) >>> 1], (p + (j * 5) + r) >>> 1);
			} else {//其他的普通情况，都是5个数
				insertSort(arr, (p + (j * 5)), ((p + (j * 5)) + 4));
				medians[indexOfMedians++] = arr[((p + (j * 5)) + 2)];
				mediansValue_index.put(arr[((p + (j * 5)) + 2)], ((p + (j * 5)) + 2));
			}
		}
		
		insertSort(medians, 0, medians.length - 1);//对已经填入所有数值的“中值数组”进行插入排序
		return mediansValue_index.get(medians[medians.length >>> 1]);//根据key(即中值数组的中值)找出value(即中值数组的中值的索引)
	}
	
	/**
	 * 插入排序
	 * @param arr
	 * @param p
	 * @param r
	 */
	public static void insertSort(int[] arr, int p, int r) {
		int value_i = 0;
		int before_i = 0;
		for (int i = p + 1; i <= r; i++) {
			value_i = arr[i];
			before_i = i - 1;
			while (before_i > p - 1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i];
				before_i--;
			}
			arr[before_i + 1] = value_i;
		}
	}
	
	/**
	 * 交换值方法
	 * @param arr
	 * @param i
	 * @param j
	 */
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}


/*
while (sp <= bigger) {//当sp>bigger,代表数组全部元素都与主元比对完毕
			if (arr[sp] <= pivot) {//sp指针指向的值，小于主元，仅右移sp
				sp++;
			} else {
				swap(arr, sp, bigger);//sp指针指向的值，大于主元，就把arr[sp]与arr[bigger]交换，再左移bigger
				bigger--;
			}
		}
		
		 * 最后跳出循环时，一定一定是bigger指向最后一个小于主元的值
		 * 并且sp指向第一个大于主元的值
		 * 所以只要把arr[p]与arr[bigger]交换，arr[p]左侧一定小于主元，右侧一定大于主元
		 * 这里的一定一定，在视频中已经讲得很清楚了：蓝桥杯第三章3.3快排单项扫描
		
		swap(arr, p, bigger);
		return bigger;//最后返回主元所在的索引
*/